#include "Segmentator.h"

#include <iostream>
#include <string>

#include "Preprocessor.h"
#include "Config.h"
#include "drawlib.h"
#include "cocoslib.h"

//#define DEBUG

void ExtractLineImagesFromDocument(PamImage* document, vector<WordsLine>* lines)
{
  #ifdef DEBUG
  cout << "Entering method ExtractLineImagesFromDocument" << endl;
  #endif
    for(vector<WordsLine> ::iterator it = lines->begin(); it != lines->end(); it++){     
	ExtractLineImageFromDocument(document, &*it);
    }
  #ifdef DEBUG
  cout << "Exiting method ExtractLineImagesFromDocument" << endl;
  #endif
}

void ExtractLineImageFromDocument(PamImage* document, WordsLine* line)
{
  #ifdef DEBUG
  cout << "Entering method ExtractLineImageFromDocument" << endl;
  #endif
  int offsetByShear = GetXOffsetFromShear(line->shear, line->top - line->bottom);
  if(offsetByShear < -line->left)offsetByShear = -line->left;   
  //cout << "Taking " << -offsetByShear << " extra pixels to compensate for shear" << endl;   
  int adjustedLeft = line->left + offsetByShear;
  int adjustedTop = line->top - line->height();
  if(adjustedTop < 0)adjustedTop = 0;
  int adjustedBottom = line->bottom + line->height();
  if(document->getHeight() < adjustedBottom) adjustedBottom = document->getHeight();
  
  //cout << "Retrieve the line image from the document image with some extra pixels on the top and the bottom" << endl;
  //cout << "In ExtractLineImageFromDocument getting subimage lineNr = " << line->lineNumber << " with (height, width) = (" << document->getWidth() << "," << document->getHeight() << ");" << endl;
  //  cout << "  (x1, y1) = (" << adjustedLeft << "," << adjustedTop << ");";
  //  cout << "  (x2, y2) = (" << line->right << "," << adjustedBottom << ");" << endl;
    
  PamImage roomyImage = document->getSubImage(adjustedLeft, adjustedTop, line->right, adjustedBottom);
  
  
  //SaveLineImage("FirstLineImage", *line, roomyImage);
  //cout << "Take the red chanel" << endl;
  PamImage* redChanelImage = GetRedChanel(&roomyImage);
  
  
  //redChanelImage->save("output/RedChanel.ppm");  
  
  //SaveLineImage("RedChanel", *line, *redChanelImage);
  int thresholdValue = determineThresholdValue(redChanelImage);
  //cout << "Threshold value determinded to be " << thresholdValue << endl;
  //cout << "Create thresholded image" << endl;
  PamImage* thresholdedImage = ThresholdGrayImage(redChanelImage, thresholdValue);
  //thresholdedImage->save("output/Thresholded.ppm");
  //cout << "Dilate the image" << endl;
 // SaveLineImage("Thresholded", *line, *thresholdedImage);
  PamImage* dilatedImage = Dilate(thresholdedImage,1);
  //SaveLineImage("Dilated", *line, *dilatedImage);
  //dilatedImage->save("output/Dilated.ppm");    
  //cout << "Trace top seperation line" << endl;
  int* topLine = GetSeperationLine(dilatedImage, line->top - adjustedTop);
  //cout << "Trace bottom seperation line" << endl;
  int* bottomLine = GetSeperationLine(dilatedImage,line->bottom - adjustedTop);
  //PamImage* firstLineDrawnImage = DrawLine(thresholdedImage, topLine);
 // PamImage* secondLineDrawnImage = DrawLine(firstLineDrawnImage, bottomLine);
  //secondLineDrawnImage->save("output/LinesDrawn.ppm");
  
 // SaveLineImage("Seperated", *line, *secondLineDrawnImage);
  //cout << "Making everything outside the trace lines white" << endl;
  RemoveBelowLine(thresholdedImage, bottomLine);
  RemoveAboveLine(thresholdedImage, topLine);
  
//  SaveLineImage("Extracted", *line, *thresholdedImage);
  //cout << "Cut of the white top and bottom of the line image" << endl;
  int newTopDelta = 0;
  int newBottomDelta = 0;
   
  ImageHistogram* histogram = makeHistogram(thresholdedImage);
  long* values = histogram->vertical;
  for(int i = 0; i < thresholdedImage->getHeight(); i++){
    if(0 < values[i])break;
    newTopDelta++;
  }
  
  for(int i = thresholdedImage->getHeight()-1; 0 <= i; i--){
    if(0 < values[i])break;
    newBottomDelta++;
  }    
  if(thresholdedImage->getHeight() < (newTopDelta + newBottomDelta)){
    cout << "Nothing found" << endl;
    //return
  }
  
  //cout << "  lineNr = " << line->lineNumber << " with (height, width) = (" << thresholdedImage->getWidth() << "," << thresholdedImage->getHeight() << ");" << endl;
  //cout << "  (x1, y1) = (" << 0 << "," << newTopDelta << ");";
  //cout << "  (x2, y2) = (" << thresholdedImage->getWidth() << "," << thresholdedImage->getHeight() - newBottomDelta << ");" << endl;
    
  PamImage cutImage = thresholdedImage->getSubImage(0, newTopDelta, thresholdedImage->getWidth(), thresholdedImage->getHeight() - newBottomDelta);
//  SaveLineImage("Cut", *line, cutImage);
  //adjust top and bottomLine
  line->top += (newTopDelta - (line->top - adjustedTop));
  line->bottom -= (newBottomDelta - (adjustedBottom - line->bottom));
  
  PamImage cleanedImage = RemoveSmallConnectedComponents(cutImage);
//  SaveLineImage("Cleaned", *line, cleanedImage);
  //cout << "Unshear image" << endl;
  PamImage unshearedImage = Shear(cleanedImage, line->shear);
//  SaveLineImage("Descheared", *line, unshearedImage);
  
  //cout << "  lineNr = " << line->lineNumber << " with (height, width) = (" << unshearedImage.getWidth() << "," << unshearedImage.getHeight() << ");" << endl;
  //cout << "  (x1, y1) = (" << -offsetByShear << "," << 0 << ");";
  //cout << "  (x2, y2) = (" << unshearedImage.getWidth() << "," << unshearedImage.getHeight() << ");" << endl;
  
  //cout << "Cut extra shear pixels" << endl;
  PamImage sizedImage = unshearedImage.getSubImage(-offsetByShear, 0, unshearedImage.getWidth(), unshearedImage.getHeight());
//  SaveLineImage("Cutagain", *line, sizedImage);
  //cout << "Remove small components" << endl;



  line->image = sizedImage;
  line->shearedImage = cleanedImage;
  SetLinePositions(line);

  //free memory
  delete dilatedImage;
  delete thresholdedImage;
  delete redChanelImage;
  delete [] topLine;
  delete [] bottomLine;
  delete [] histogram->horizontal;
  delete [] histogram->vertical;
  delete histogram;
  #ifdef DEBUG
  cout << "Exiting method ExtractLineImageFromDocument" << endl;
  #endif
}

PamImage* DrawLine(PamImage* image, int* line){
  int width = image->getWidth();  
  PamImage* outputImage = image->convert(RGB_IMAGE);
  RGBPixel** pixels = outputImage->getRGBPixels();
  for(int x = 0; x < width; x++) {
    int y = line[x];
    pixels[y][x].r = 0;
    pixels[y][x].g = 255;
    pixels[y][x].b = 0;
  }
  return outputImage;
}

void DetermineWordPositions(vector<WordsLine>* lines)
{
  #ifdef DEBUG
  cout << "Entering method DetermineWordPositions" << endl;
  #endif
    for(vector<WordsLine> ::iterator it = lines->begin(); it != lines->end(); it++)
    {
      DetermineWordPositions(&*it);
    }
  #ifdef DEBUG
  cout << "Exiting method DetermineWordPositions" << endl;
  #endif
}

void DetermineWordPositions(WordsLine* line)
{
  #ifdef DEBUG
  cout << " Entering method DetermineWordPositions (in one line)" << endl;
  #endif
  //if(line->image == NULL)return;
  if(0 < line->words.size()){
     if(Config::getInstance()->useGivenBoundariesWhenPossible)return;
    //cout << "already words in this line, need to determine words hypotheses, so will just ditch them and determine them again" << endl;
    line->words.clear();
  }
  vector<WordSeperation*> seperations = getSeperations(line);   
   
  vector<WordSeperation*> potentialStartSeperations;
  int wordNr = 1;
  for(vector<WordSeperation*> ::iterator it = seperations.begin(); it != seperations.end(); it++){     
    WordSeperation* currentSeperation = *it;
    if(currentSeperation->runLength <= Config::getInstance()->wordSeperationHypotheseMinimumGapWidth){
      if(potentialStartSeperations.size() == 0){
	potentialStartSeperations.push_back(currentSeperation);
      }
      continue;
    }
    for(vector<WordSeperation*> ::iterator it2 = potentialStartSeperations.begin(); it2 != potentialStartSeperations.end(); it2++){     
      WordSeperation* currentStartSeperation = *it2;
      int top = line->top;
      int bottom = line->bottom;
      int left = line->left + currentStartSeperation->xPosition;
      int right = line->left + currentSeperation->xPosition;
      int shear = line->shear;
      string text = "to be classified";
      if(Config::getInstance()->wordSeperationUseShearedImage){
	int shearOffset = GetXOffsetFromShear(line->shear, (bottom - top)-line->base);
	if(shearOffset < 0) shearOffset *= -1;
	cout << shearOffset << " " << (bottom - top)-line->base << endl;
	left -= shearOffset;
	right -= shearOffset;
      }
      Word word(top, bottom, left, right, shear, text, line->lineNumber, wordNr, line->documentName);
      line->words.push_back(word);
      wordNr++;
    }
    if(Config::getInstance()->wordSeperationHypotheseThresholdWidth < currentSeperation->runLength){
      potentialStartSeperations.clear();
    }   
    potentialStartSeperations.push_back(currentSeperation);
  }
  
  //free memory
  for(unsigned i = 0; i < seperations.size(); i++) delete seperations[i];
  #ifdef DEBUG
  cout << " Exiting method DetermineWordPositions (in one line)" << endl;
  #endif
}

class ConnectedComponentDescriptionCompare
{
  public:
  bool operator() (const ConnectedComponentDescription first, const ConnectedComponentDescription second) const {
    return first.left > second.left;
  }
};
/*
vector<WordSeperation*> getSeperations(WordsLine* line){
  Cocos cocos(&line->image,8,0);  
  int cocosNum = cocos.getNum();  
  bool componentRemoved = true;
  while(componentRemoved){
    componentRemoved = false;
    for(int i = 0; i < cocosNum; i++){
      bool overlapFound = false;
      long left, right, top, bottom, currentleft, currentright, currenttop, currentbottom;
      cocos.getCocoRect(i, left, top, right,bottom);
      for(int j = 0; j < cocosNum; j++){
	cocos.getCocoRect(j, currentleft, currenttop, currentright, currentbottom);
	if(currentleft < left && right < currentright){
	  overlapFound = true;
	  break;
	}
      }
      if(overlapFound){
	cocos.remove(i);
	componentRemoved = true;
	break;
      }
    }
    cocosNum = cocos.getNum(); 
  }
  
  priority_queue<ConnectedComponentDescription, vector<ConnectedComponentDescription>, ConnectedComponentDescriptionCompare> descriptions;
  for(int i = 0; i < cocosNum; i++){
    long dummy;
    ConnectedComponentDescription description;
    cocos.getCocoRect(i, description.left, dummy, description.right, dummy);
    descriptions.push(description);
  }
  
  vector<WordSeperation*> seperations; 
  ConnectedComponentDescription previousDescription;
  ConnectedComponentDescription description;
  previousDescription.left = 0;
  previousDescription.right = 0;
  while(0 < descriptions.size()){
    description = descriptions.top();
    descriptions.pop();
    WordSeperation* currentSeperation = new WordSeperation;
    currentSeperation->xPosition = previousDescription.right + 1;
    currentSeperation->runLength = description.left - previousDescription.right;
    seperations.push_back(currentSeperation);	
    previousDescription = description;
  }
  WordSeperation* currentSeperation = new WordSeperation;
  currentSeperation->xPosition = previousDescription.right;
  currentSeperation->runLength = line->right - previousDescription.right;
  seperations.push_back(currentSeperation);	
  return seperations;
}
*/
vector<WordSeperation*> getSeperations(WordsLine* line){
 vector<WordSeperation*> seperations;  
 bool isInRun = false;
  WordSeperation* currentSeperation;
  PamImage image;
  if(Config::getInstance()->wordSeperationUseShearedImage){    
    image = line->shearedImage;
  }else{
    image = line->image;
  }
  
  int width = image.getWidth();
  int height = image.getHeight();
  if(Config::getInstance()->wordSeperationOnlyLookBetweenBaseAndXLine){
    for(int i = 0; i < line->x; i++){
      line_gray(image, 0, i, width, i, 255);
    }
    for(int i = line->base; i < height; i++){
      line_gray(image, 0, i, width, i, 255);
    }
  }
  ImageHistogram* histogram = makeHistogram(&image);
  long* values = histogram->horizontal;
  
  for(int i = 0; i < line->image.getWidth(); i++){
    if(0 == values[i]){
      if(isInRun){
	currentSeperation->runLength++;
      }else{
	isInRun = true;
	currentSeperation = new WordSeperation;
	currentSeperation->xPosition = i;
	currentSeperation->runLength = 1;
	seperations.push_back(currentSeperation);	
      }
    }else{
      if(isInRun){
	isInRun = false;
      }
    }
  }  
  delete [] histogram->horizontal;
  delete [] histogram->vertical;
  delete histogram;
  return seperations;
}

void ExtractWordImages(vector<WordsLine>* lines){
  #ifdef DEBUG
  cout << "Entering method ExtractWordImages" << endl;
  #endif
    for(vector<WordsLine> ::iterator it = lines->begin(); it != lines->end(); it++){     
	ExtractWordImages(&*it);
    }
  #ifdef DEBUG
  cout << "Exiting method ExtractWordImages" << endl;
  #endif
}

void ExtractWordImages(WordsLine* line){    
  #ifdef DEBUG
  cout << " Entering method ExtractWordImages (in one line)" << endl;
  #endif    
  //if(line->image == NULL)throw exception(); //line image not yet set (use ExtractImageFromDocument first)
  if(line->words.size() == 0){
    cout << "No words in the line..." << endl;
  }//word positions not yet known (use SetWordPositions first)
  for(vector<Word> ::iterator it = line->words.begin(); it != line->words.end(); it++){     
    Word* word = &*it;
    if(word->top != line->top){ //fix coordinates so the extra x offset by the shear in combination with more height is undone
	int offsetByShear = GetXOffsetFromShear(word->shear, line->top - word->top);
	word->left -= offsetByShear;
	word->top = line->top;
	word->right -= offsetByShear;
	word->bottom = line->bottom;
    }  
    
    //#ifdef DEBUG
    //cout << "In ExtractWordImages getting subimage lineNr = " << line->lineNumber << " width (height, width) = (" << line->image.getWidth() << "," << line->image.getHeight() << ");" << endl;
    //cout << "  (x1, y1) = (" << word->left - line->left << "," << word->top - line->top << ");";
    //cout << "  (x2, y2) = (" << word->right - line->left << "," << word->bottom - line->top << ");" << endl;
    //#endif
    
    word->image = line->image.getSubImage(word->left - line->left, word->top - line->top, word->right - line->left, word->bottom - line->top);
    
    #ifdef DEBUG
    cout << "  clipping" << endl;
    #endif
    
    word->image = Clip(word->image);
  }
  #ifdef DEBUG
  cout << " Exiting method ExtractWordImages (in one line)" << endl;
  #endif    
}

void SetLinePositions(WordsLine* line){
  PamImage lineImage = line->image;
  //int width = lineImage.getWidth();
  int height = lineImage.getHeight();  
  ImageHistogram* histogram = makeHistogram(&lineImage);
  long* values = histogram->vertical;
  long avarage = 0;
  for(int i = 0; i < height; i++){
    avarage += values[i];
  }
  avarage /= height;
  
  vector<int> exceedAvaragePositions;
  vector<int> dropUnderAvaragePositions;
  
  bool currentlyBelow = true;
  for(int i = 0; i < height; i++){
    if(avarage < values[i]){
      if(!currentlyBelow)continue;
      currentlyBelow = false;
      exceedAvaragePositions.push_back(i);
    }else{
      if(currentlyBelow)continue;
      currentlyBelow = true;
      dropUnderAvaragePositions.push_back(i);
    }
  }  
 // cout << "number of exceed: " << exceedAvaragePositions.size() << " number of drop: " << dropUnderAvaragePositions.size() << endl;
  int topXLinePosition = 0;
  int topBaseLinePosition = height - 1;
  int topScore = ScoreBaseAndXPosition(values, avarage, topXLinePosition, topBaseLinePosition, height);
  
//  cout << "initscore: " << topScore << endl;  
  for(unsigned i = 0; i < exceedAvaragePositions.size(); i++){
    int currentXLinePosition = exceedAvaragePositions[i];
    for(unsigned j = 0; j < dropUnderAvaragePositions.size(); j++){
       int currentBaseLinePosition = dropUnderAvaragePositions[j];
       if(currentBaseLinePosition <= currentXLinePosition)continue;
       int currentScore = ScoreBaseAndXPosition(values, avarage, currentXLinePosition, currentBaseLinePosition, height);
    //   cout << "test X: " << currentXLinePosition << " base: " << currentBaseLinePosition << " score:" << currentScore << endl;
       if(topScore < currentScore){
	 topScore = currentScore;
	 topBaseLinePosition = currentBaseLinePosition;
	 topXLinePosition = currentXLinePosition;
       }
    }
  }
  line->x = topXLinePosition;
  line->base = topBaseLinePosition;
 // cout << "X: " << topXLinePosition << " base: " << topBaseLinePosition << " score:" << topScore << endl;
} 

int ScoreBaseAndXPosition(long* values, long avarage, int xPosition, int basePosition, int height){  
  int score = 0;
  for(int i = 0; i < height; i++){
    if(xPosition <= i && i < basePosition){
      if(avarage <= values[i]){
	score++;
      }
    }else{
      if(values[i] <= avarage){
	score++;
      }      
    }
  }
  return score;
}

PamImage Clip(PamImage& image){
  int width = image.getWidth();  
  int height = image.getHeight();
  ImageHistogram* histogram = makeHistogram(&image);
  long* horizontalValues = histogram->horizontal;
  long* verticalValues = histogram->vertical;
  int top = 0;
  for(; top < height && verticalValues[top] == 0; top++);
  int bottom = height-1;
  for(; 0 < bottom && verticalValues[bottom] == 0; bottom--);
  int left = 0;
  for(; left < width && horizontalValues[left] == 0; left++);
  int right = width-1;
  for(; 0 < right && horizontalValues[right] == 0; right--);
  return image.getSubImage(left, top, right, bottom);
}

void RemoveBelowLine(PamImage* image, int* line){
  #ifdef DEBUG
  cout << "Entering method RemoveBelowLine" << endl;
  #endif    
  int width = image->getWidth();  
  int height = image->getHeight();
  for(int i = 0; i < width; i++) line_gray(*image, i, line[i], i, height, 255);  
  #ifdef DEBUG
  cout << "Exiting method RemoveBelowLine" << endl;
  #endif    
}

void RemoveAboveLine(PamImage* image, int* line){
  #ifdef DEBUG
  cout << "Entering method RemoveAboveLine" << endl;
  #endif    
  int width = image->getWidth();  
  for(int i = 0; i < width; i++) line_gray(*image, i, 0, i, line[i], 255);  
  #ifdef DEBUG
  cout << "Exiting method RemoveAboveLine" << endl;
  #endif    
}

int* ToYArray(int width, AStarPixel* line){
  #ifdef DEBUGASTAR
  cout << "Entering method ToYArray" << endl;
  #endif    
  int* yPositionArray = new int[width];
  for(int i = 0; i < width; i++)yPositionArray[i] = 0;
  AStarPixel* currentLine = line; 
  while(currentLine != NULL){// && 0 <= currentLine->xPosition && currentLine->xPosition < width){
    int xIndex = currentLine->xPosition;
    int yIndex = currentLine->yPosition;
    yPositionArray[xIndex] = yIndex;
    currentLine = currentLine->previousPixel;
  }
  #ifdef DEBUGASTAR
  cout << "Exiting method ToYArray" << endl;
  #endif    
  return yPositionArray;
}

class AStarCompare
{
  public:
  bool operator() (const AStarPixel* lhs, const AStarPixel* rhs) const {
    return lhs->fScore > rhs->fScore;
  }
};

int* GetSeperationLine(PamImage* image, int linePosition)
{
  #ifdef DEBUG
  cout << "Entering method GetSeperationLine" << endl;
  #endif    
  //cout << "Calculating best line to seperate two lines..." << endl;  
  int width = image->getWidth();
  int height = image->getHeight();
  
  //set the boundaries of the search
  ImageHistogram* histogram = makeHistogram(image);
  long* values = histogram->vertical;
  long avarage = 0;
  for(int i = 0; i < height; i++){
    avarage += values[i];
  }
  avarage /= height;  
  int maxTopDeviation = 0;
  for(int i = linePosition; 0 < i && values[i]< avarage; i--){
    maxTopDeviation++;
  }  
  int maxBottomDeviation = 0;
  for(int i = linePosition; i < height && values[i] < avarage; i++){
    maxBottomDeviation++;
  }  
  
  maxTopDeviation += 20;
  maxBottomDeviation += 20;
  //cout << "Setting the maximum deviation to the top at " << maxTopDeviation << "and the maximum deviation to the bottom at: " << maxBottomDeviation << endl;
  
  priority_queue<AStarPixel*, vector<AStarPixel*>, AStarCompare> openSet;
  AStarPixel** pixels = new AStarPixel*[width];
  for (int i = 0; i < width; i++) {
        pixels[i] = new AStarPixel[height];
  }
  for(int xIndex = 0; xIndex < width; xIndex++){
    for(int yIndex = 0; yIndex < height; yIndex++){
      pixels[xIndex][yIndex].xPosition = xIndex;
      pixels[xIndex][yIndex].yPosition = yIndex;
      pixels[xIndex][yIndex].isBlack = (image->getPixelGray(xIndex, yIndex) == 0);
      pixels[xIndex][yIndex].isClosed = false;
      pixels[xIndex][yIndex].isOpen = false;
    }
  }
  
  AStarPixel* finish = &(pixels[width-1][linePosition]);
  AStarPixel* start = &(pixels[0][linePosition]);
  start->gScore = 0;
  start->hScore = GetHeuristicDistance(start, finish);
  start->fScore = start->hScore;
  start->previousPixel = NULL;
  start->isOpen = true;
  openSet.push(start);
  int* result = NULL;
  while(true){
    //get the node with the lowest fscore
    AStarPixel* currentPixel = openSet.top();
    openSet.pop();
    currentPixel->isClosed = true;
    currentPixel->isOpen = false;
    
    if(currentPixel == finish){
      //cout << "FOUND A PATH!" << endl;
      result = ToYArray(width, currentPixel);
      break;
    } 
    
    //for all neighbournodes
    int xIndex = currentPixel->xPosition - 1; 
    if(xIndex < 0) xIndex = 0;
 
    int yIndex = currentPixel->yPosition - 1;
    if(yIndex < 0) yIndex = 0;
    if(yIndex < (linePosition - maxTopDeviation)) yIndex = (linePosition - maxTopDeviation); 
  
    int toXIndex = (currentPixel->xPosition + 1);
    if(width <= toXIndex) toXIndex = width - 1;
    
    int toYIndex = (currentPixel->yPosition + 1);
    if(height <= toYIndex) toYIndex = height - 1;
    if((linePosition + maxBottomDeviation) < toYIndex) toYIndex = (linePosition + maxBottomDeviation);
    
    for(int xIndex2 = xIndex;xIndex2 <= toXIndex; xIndex2++){
      for(int yIndex2 = yIndex;yIndex2 <= toYIndex; yIndex2++){
	AStarPixel* currentNeighbourPixel = &(pixels[xIndex2][yIndex2]);
	if(!currentNeighbourPixel->isClosed){
	  double tentativeGScore = currentPixel->gScore;
	  if(currentNeighbourPixel->isBlack)
    {
	    tentativeGScore+=Config::getInstance()->lineSeperationBlackPixelWeight;
	  }
    else
    {
	    tentativeGScore+=Config::getInstance()->lineSeperationWhitePixelWeight;
	  }
	  if(!currentNeighbourPixel->isOpen
	    || tentativeGScore < currentNeighbourPixel->gScore){
	    currentNeighbourPixel->previousPixel = currentPixel;
	    currentNeighbourPixel->gScore = tentativeGScore;
	    currentNeighbourPixel->hScore = GetHeuristicDistance(currentNeighbourPixel, finish);		  
	    currentNeighbourPixel->fScore = currentNeighbourPixel->gScore + currentNeighbourPixel->hScore;
	    currentNeighbourPixel->isClosed = false;
	  }
	  if(!currentNeighbourPixel->isOpen){
	    openSet.push(currentNeighbourPixel);
	    currentNeighbourPixel->isOpen = true;
	  }
	}
      }
    }      
  }  
  
  //free memory 
  for(int xIndex = 0; xIndex < width; xIndex++){
    delete [] pixels[xIndex];
  }
  delete [] pixels;
  delete [] histogram->horizontal;
  delete [] histogram->vertical;
  delete histogram;
  #ifdef DEBUG
  cout << "Exiting method GetSeperationLine" << endl;
  #endif    
  return result;
}

double GetHeuristicDistance(AStarPixel* first, AStarPixel* second){  
  #ifdef DEBUGASTAR
  cout << "Entering method GetHeuristicDistance" << endl;
  #endif    
  double deltaX = second->xPosition - first->xPosition;
  double deltaY = second->yPosition - first->yPosition;
  if(deltaX < 0)deltaX = - deltaX;
  if(deltaY < 0)deltaY = - deltaY;
  #ifdef DEBUGASTAR
  cout << "Exiting method GetHeuristicDistance" << endl;
  #endif    
  return deltaX + (deltaY * Config::getInstance()->lineSeperationDeviationWeightFactor);
 // return sqrt((deltaX*deltaX)+(deltaY*deltaY));
}



ImageHistogram* makeHistogram(PamImage* image){
  #ifdef DEBUG
  cout << "Entering method makeHistogram" << endl;
  #endif    
  int threshold = 150;
  int width;
  width = image->getWidth();
  int height = image->getHeight();
  long *horizontalhistogram = new long[width];
  long *verticalhistogram = new long[height];
  
  for (long yindex = 0; yindex < height; ++yindex)
    verticalhistogram[yindex] = 0;
  
  for (long xindex = 0; xindex < width; ++xindex)
    horizontalhistogram[xindex] = 0;
  
  for (long yindex = 0; yindex < height; ++yindex) {
    int inkRunLength = 0;
    double maxInkLength = -1;
    for (long xindex = 0; xindex < width; ++xindex) {
      GrayPixel pixel;
	pixel = image->getPixelGray(xindex, yindex);
      if(pixel < threshold) {	
         inkRunLength++;
         horizontalhistogram[xindex]++;
         verticalhistogram[yindex]++;
      }
      else {
	if(maxInkLength < inkRunLength)
	  maxInkLength = inkRunLength;
	inkRunLength = 0;
      }
    }
    
    // scale histogram using ink running length
    //verticalhistogram[yindex] = (long)(verticalhistogram[yindex] / maxInkLength);
  }
  
  ImageHistogram * histo = new ImageHistogram;
  histo->horizontal = horizontalhistogram;
  histo->vertical   = verticalhistogram;
  #ifdef DEBUG
  cout << "Exiting method makeHistogram" << endl;
  #endif    
  return histo;
}

vector< double> makeDesityHistogram(PamImage* image)
{
  #ifdef DEBUG
  cout << "Entering method makeDesityHistogram" << endl;
  #endif    

  vector< double> historgram(256,0);
  long width  = image->getWidth();
  long height = image->getHeight();
   
  for (long yindex = 0; yindex < height; ++yindex) 
    for (long xindex = 0; xindex < width; ++xindex) 
    {
      GrayPixel pixel;
	    pixel = image->getPixelGray(xindex, yindex);
      historgram[pixel] += 1.0;
    }

  #ifdef DEBUG
  cout << "Exiting method makeDesityHistogram" << endl;
  #endif    
  return historgram;
}

int determineThresholdValue(PamImage* image)
{
  //alternative;
  return Config::getInstance()->threshold;  

  #ifdef DEBUG
  cout << "Entering method determineThresholdValue" << endl;
  #endif    

  vector< double> denstiyhistogram = makeDesityHistogram(image);

  int bestthreshold = 0;
  double bestfscore = 0;
  double newfscore  = 0;
  for (size_t index = 0; index < 256; ++index)
  {
    newfscore = getFscore(denstiyhistogram, index);
    if (bestfscore < newfscore)
    {
      bestfscore = newfscore;
      bestthreshold = index;
    }
  }

  //cout << "Threshold: " << bestthreshold << endl;

  #ifdef DEBUG
  cout << "Exiting method determineThresholdValue" << endl;
  #endif

  return bestthreshold;    
}

double getFscore(vector< double> histogram, size_t lastoffirstclass)
{

  vector< double> firstgroup(256, 0.0);
  vector< double> secondgroup(256,0.0);
  for (size_t index = 0; index < histogram.size(); index++)
    if (index > lastoffirstclass)
      secondgroup[index] = histogram[index];
    else
      firstgroup[index]  = histogram[index];

 
  double allmean    = mean(histogram);
  double allsum     = sum(histogram);

  double firstmean  = mean(firstgroup);
  double firstsum   = sum(firstgroup);


  double secondmean = mean(secondgroup);
  double secondsum  = allsum - firstsum;



  double betweenvariance  = firstsum  * ((firstmean - allmean)  * (firstmean - allmean)) + 
                            secondsum * ((secondmean - allmean) * (secondmean - allmean));

  double withinvariance   = (variance(firstgroup) + variance(secondgroup)) / (allsum - 2.0);


  double fscore = betweenvariance / withinvariance;

  if (firstsum   == 0.0)
    fscore = 0;
  if (secondsum  == 0.0)
    fscore = 0;
  
  return fscore;

}

double sum(vector< double> data)
{
    double sum = 0;
    for (size_t i = 0; i < data.size(); i++)
        sum += data[i];
    return sum;
}

double mean(vector< double> data)
{
    double datasum = 0;
    for (size_t i = 0; i < data.size(); i++)
        datasum += (data[i]) * ((double)i);
    return datasum / sum(data);
}

double variance(vector< double> data)
{
    double datamean = mean(data);
    double variance = 0;
    for (size_t i = 0; i < data.size(); i++)
        variance += (data[i]) *(((double)i) - datamean) * (((double)i) - datamean);
    return variance / ((double)(sum(data) - 1.0));
}


